//
// Created by francklinson on 2021/7/25 AT 10:39.
//
#include <iostream>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
private:
    int ans = 0;

public:
    int maxAncestorDiff(TreeNode *root) {
        dfs(root, root->val, root->val);
        return ans;
    }

    /**
     * dfs向下传递的过程中，保留路径上的最大最小值信息，实时更新
     * @param root
     * @param up
     * @param down
     */
    void dfs(TreeNode *root, int up, int down) {
        if (root == nullptr) return;
        // 更新最值
        up = max(up, root->val);
        down = min(down, root->val);
        // 更新结果
        ans = max(ans, up - down);
        // 对子树递归搜索
        dfs(root->left, up, down);
        dfs(root->right, up, down);
    }
};

int main() {
    auto n1 = TreeNode(8), n2 = TreeNode(3), n3 = TreeNode(10), n4 = TreeNode(1), n5 = TreeNode(6),
            n6 = TreeNode(14), n7 = TreeNode(4), n8 = TreeNode(7), n9 = TreeNode(13);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    n3.right = &n6;
    n5.left = &n7;
    n5.right = &n8;
    n6.left = &n9;
    Solution solution;
    cout << solution.maxAncestorDiff(&n1) << endl;
    return 0;
}

